//因为是完整二叉树，所以用数组表示数中的结点
//编号为k结点的父母结点编号为k/2，其两个子节点分别为2k和2k+1
//swim操作，将一个节点与其父节点进行比较，如果他比父节点更大了，那么交换，然后再比较，直到其变为根节点或者父节点比他大
//插入操作的时候，只需把新的结点插入到末尾，然后对其进行swim操作即可
//sink操作，对于一个k，将其于两个子节点中较大的进行比较，如果他更小，那么交换，然后再再进行比较。
//删除最大值的时候，就是存储最顶端的元素用于之后返回，然后将其与末尾元素交换并改为null，然后对交换后的最顶端元素进行sink操作
public class Binaryheap extends Sort{
   int data[];     //储存所有元素 第零个位置舍弃
   int size;       //返回有效的储存元素  新元素就插在size的位置
   int maxN;       //返回存储空间
 public Binaryheap()
 {}
  public Binaryheap(int n)
  {
     maxN=n;
     size=0;
     data=new int[n];
  }

  public void swim(int k)
  {
     while(true)
     {
        if(k<=0)
        {
            break;
        }
        else
        {
            if(data[k]>data[k/2])
            {
                Exchange(data,k,k/2);
                k/=2;
            }
            else
            {
                break;
            }
        }
     }
  }   

  public void Insert(int newNumber)
  {
     if(size==maxN)
     {
        System.out.printf("already full");
        return ;
     }
     else
     {
       data[size]=newNumber;
       swim(size);
       size++;
     }
  }

  public void sink(int k)
  {
    k++;                       //k是逻辑上的位置
    while(true)
    {
     int j=2*k;                //找到逻辑上k子结点的编号
     if(j>size)                //j-1是物理上子结点的位置 j-1需要小于或等于size-1，因为size代表最后一个元素再后一个的偏移量
     {
        return;
     }
     if(j<=size-1&&data[j-1]<data[j])   //如果逻辑上j+1的位置在物理上存在，并且还大于j对应的节点
     {
        j++;
     }
     
     if(data[k-1]<data[j-1])
     {
        Exchange(data,k-1,j-1);
        k=j;
     }
     else
     {
        return;
     }
    }
  }

  public int DelMax()
  {
     int max=data[0];
     Exchange(data,0,size-1);
     size--;
     sink(0);
     return max;
  }

   public static void main(String[] args) throws Exception {
    Binaryheap Bh=new Binaryheap(10);
    Bh.Insert(2);
    Bh.Insert(3);
    Bh.Insert(6);
    Bh.Insert(5);
    Bh.Insert(1);
    int max1=Bh.DelMax();
    int max2=Bh.DelMax();
    int max3=Bh.DelMax();
   }
}
